Recent advances in optical networking technology have pushed line card data transfer rates in high speed IP routers to 40 Gbits/s (gigabits per second), and even higher data rates are expected in the near term. Given such high data rates, packet forwarding in high speed IP routers must necessarily be done in hardware. Current hardware-based solutions for high speed packet forwarding fall into two main categories, namely, ASIC-based solutions and ternary CAM (Content-Addressable Memory) or TCAM-based solutions. (Network processor-based solutions are also being considered for high speed packet forwarding, although network processors that can handle 40 Gbits/s wire speeds are not yet generally available.) ASIC-based architectures typically implement a data structure known as a “routing trie” using some sort of high speed memory such as SRAMs. As is well known to those skilled in the art, a routing trie is a tree-based data structure used to store routing prefixes for use in longest prefix matching. (As is also well known to those of ordinary skill in the art, longest prefix matching is used to determine to which neighboring network node a packet with a given destination should be forwarded.) If a single SRAM memory block is used to store the entire routing trie, multiple accesses (one per routing trie level) are required to forward a single packet. This can slow down lookups considerably, and the forwarding engine may not be able to process incoming packets at the line rate. Recently, however, it has been proposed that forwarding speeds can be significantly increased if pipelining is used in ASICA-based forwarding engines. This is because with multiple stages in the pipeline (e.g., one stage per trie level), one packet can be forwarded during every memory access time period.
In addition, pipelined ASICs that implement routing tries provide a general and flexible architecture for a wide variety of forwarding and classification tasks. This is a major advantage in today's high end routers which have to provide packet flow classification and filtering, as well as multicast and IPv6 routing in addition to the standard IPv4 routing functions. (IPv4 and IPv6 represent Internet Protocol versions 4 and 6, respectively, and are each fully familiar to those of ordinary skill in the art.) Since longest prefix matching is the technique common to all of these tasks, the same pipelined hardware can be used to perform them all efficiently, thereby producing significant savings in cost, complexity and space.
Despite the advantages of pipelined ASIC architectures, managing routing tries during route updates in such architectures is difficult. Although one way to simplify management would be to use double buffering—that is, to create a duplicate copy of the lookup trie and use one for lookups and the other for updates—the memory required would obviously be doubled, thereby doubling the relatively expensive SRAM cost. Therefore, a pipelined ASIC-based architecture which employs a single routing trie amenable to efficient incremental updates is preferable.
In co-pending U.S. patent application Ser. No. 10/175,461, “Method And Apparatus For Generating Efficient Data Structures For Use In Pipelined Forwarding Engines,” filed by A. Basu et al. on Jun. 19, 2002 and commonly assigned to the assignee of the present invention, it was recognized that to provide for a pipelined ASIC-based forwarding engine architecture which is amenable to efficient incremental updates, it would be advantageous to design and generate the associated routing trie such that the memory allocated to the trie is evenly balanced across the multiple pipeline stages. In this manner, incremental updates to the trie are more likely to require memory modifications which are evenly distributed across the memory of the different pipeline stages, thereby taking advantage of the parallel processing capabilities inherent in such a pipelined architecture. U.S. patent application Ser. No. 10/175,461 is hereby incorporated by reference as if fully set forth herein.
Nonetheless, despite the use of efficient routing trie data structures such as those which may, for example, be generated in accordance with the disclosure of U.S. patent application Ser. No. 10/175,461, route updates occur quite frequently and can, in general, still be quite disruptive to the process of fast path lookup performed by a pipelined forwarding engine. Therefore, even given such a well-designed routing trie, it would further be highly advantageous to reduce such disruption by providing for more efficient incremental route updates.